package com.comp6521.project01;

public class Quicksort {

	
	public static void quickSort(int[] data, int length) {
		recQuickSort(data, 0, length-1);
	}
	
	private static void recQuickSort(int[] data,int left, int right) {
		if(right-left <= 0){ 
			return;
		}
		else {
			long pivot = data[right];
			int partition = partitionIt(data, left, right, pivot);
			recQuickSort(data, left, partition-1);
			recQuickSort(data, partition+1, right);
		}
	}
	
	private static int partitionIt(int[] data, int left, int right, long pivot) {
		int leftPtr = left-1;
		int rightPtr = right;	
		while(true) { 
			while(data[++leftPtr] < pivot )
				;
			while(rightPtr > 0 && data[--rightPtr] > pivot)
				;
			if(leftPtr >= rightPtr){
				break;
			}
			else{
				swap(data, leftPtr, rightPtr);
			}
		}
		swap(data, leftPtr, right);
		return leftPtr;
	}
	
	private static void swap(int[] data, int dex1, int dex2) {
		int temp = data[dex1];
		data[dex1] = data[dex2];
		data[dex2] = temp;
	}
}
